198. House Robber

Similar Question

Solution Tips

方案一: 动态规划

步骤一: 定义子问题

步骤二: 写出子问题的递推关系

步骤三: 确定 DP 数组的计算顺序

var rob = function(nums) {
    // 1. 定义 dp[i] 为偷前 i 家, 能获得最大价值
    // 2. dp[i] = money[i] + dp[i - 2], 偷了这家就只能偷前前家了
    const dp = Array.from({ length: nums.length }, () => 0);
    if (nums.length === 1) {
        return nums[0];
    }
    // 3. 第一家和第二家就只能偷自己的
    dp[0] = nums[0];
    // 这里究竟应该是 nums[1] 还是取 max 呢? 取 max 其实是 ok 的, 对于 nums[2], 反正都不会参考 nums[1]
    // 对于 nums[3], 要参考 nums[1] 时, 无论打劫的是第一家还是第二家都是符合题意的
    dp[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        // dp[i] = nums[i] + dp[i - 2];
        // 根据 dp[i] 的定义, 如果不偷这一家的收益更大, 那么就不应该偷的
        dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
    }
    // console.log(dp.concat());
    // return Math.max(dp[nums.length - 1], nums[nums.length - 2]);
    return dp[nums.length - 1];
};
console.log(rob([2,7,9,3,1]));
// console.log(rob([1,2,3,1]));